/*
 * @lc app=leetcode.cn id=23 lang=typescript
 *
 * [23] 合并K个升序链表
 */

// @lc code=start

// Definition for singly-linked list.
// class ListNode {
//   val: number;
//   next: ListNode | null;
//   constructor(val?: number, next?: ListNode | null) {
//     this.val = val === undefined ? 0 : val;
//     this.next = next === undefined ? null : next;
//   }
// }

class MinPQ<T extends ListNode> {
  pq: Array<T>;
  constructor() {
    this.pq = [];
  }
  less(i: number, j: number): boolean {
    return this.pq[i].val < this.pq[j].val;
  }
  swap(i: number, j: number): void {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  swin(k: number): void {
    let parentIdx = (k - 1) >> 1;
    while (parentIdx >= 0 && this.less(k, parentIdx)) {
      this.swap(k, parentIdx);
      k = parentIdx;
      parentIdx = (k - 1) >> 1;
    }
  }
  size(): number {
    return this.pq.length;
  }
  sink(k: number): void {
    let childIdx = k * 2 + 1;
    while (childIdx < this.size()) {
      if (childIdx + 1 < this.size() && this.less(childIdx + 1, childIdx)) {
        childIdx++;
      }
      if (this.less(k, childIdx)) break;
      this.swap(k, childIdx);
      k = childIdx;
      childIdx = k * 2 + 1;
    }
  }
  top(): T {
    return this.pq[0];
  }
  push(k: T): void {
    this.pq.push(k);
    this.swin(this.size() - 1);
  }
  pop(): T {
    if (this.size() === 0) return;
    const min = this.pq[0];
    this.swap(0, this.size() - 1);
    this.pq.pop();
    this.sink(0);
    return min;
  }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  // 小顶堆
  // 多路归并
  const minPQ = new MinPQ<ListNode>();
  const dump = new ListNode();
  let p = dump;
  for (const node of lists) {
    if (node === null) continue;
    minPQ.push(node);
  }
  while (minPQ.size()) {
    const min = minPQ.pop();
    p.next = min;
    p = p.next;
    if (min.next) minPQ.push(min.next);
  }

  return dump.next;
}
// @lc code=end
